package com.cty._02_HighQualityCode._18_02_DeleteDuplicateNodeInList;

/**
 * @Auther: cty
 * @Date: 2020/7/5 12:44
 * @Description: 面试题18（二）：删除链表中重复的结点
 * 题目：在一个排序的链表中，如何删除重复的结点？例如，在图3.4（a）中重复
 * 结点被删除之后，链表如图3.4（b）所示。
 * @version: 1.0
 */
class LinkedList {
    private ListNode first;

    public LinkedList(){
        first = null;
    }

    public boolean isEmpty(){
        return (first == null);
    }

    public void displayList(){
        ListNode current = first;
        while(current != null){
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public void insertFirst(ListNode node){
        node.next = first;
        first = node;
    }

    /**
     * 删除重复节点
     */
    public void deleteDuplicateNode(){
        if(isEmpty())
            return;

        ListNode previous = null;
        ListNode current = first;

        while(current != null){
            boolean needDelete = false;
            ListNode next = current.next;
            if(next != null && current.value==next.value)
                needDelete = true;

            if(!needDelete){
                previous = current;
                current = current.next;
            }else{
                int value = current.value;
                ListNode toBeDeleted = current;
                while(toBeDeleted!=null && toBeDeleted.value==value){
                    next = toBeDeleted.next;
                    toBeDeleted = next;
                }

                if(previous == null)
                    first = next;
                else
                    previous.next = next;
                current = next;
            }  // end else

        }  // end while
        return;
    }  // end deleteDuplicateNode()

}  // end class

class ListNode{
    int value;
    ListNode next;

    public ListNode(){}

    public ListNode(int value){
        this.value = value;
    }
}  // end class
